#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef tuple<int,int,int> tpi;
class dsu{
  private:
    vector<int> f,s;
  public:
    dsu(int n){
      f.resize(n),s.resize(n,1);
      iota(f.begin(),f.end(),0);
    }
    inline int leader(int x){
      return x==f[x]?x:f[x]=leader(f[x]);
    }
    inline void merge(int x,int y){
      x=leader(x),y=leader(y);
      if(x==y)return;
      if(s[x]>s[y])swap(x,y);
      f[x]=y,s[y]+=s[x];
    }
    inline bool same(int x,int y){
      return leader(x)==leader(y);
    }
};
main(){
  freopen("up.in","r",stdin);
  freopen("up.out","w",stdout);
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin>>t;
  while(t--){
    int n,m,r=0,l=0,c=0; cin>>n>>m;
    if(!m){cout<<n-1<<'\n'; continue;}
    vector<tpi> e;
    set<pair<int,int> > s;
    for(int i=0;i<m;i++){
      int u,v,w; cin>>u>>v>>w,u--,v--;
      if(u>v)swap(u,v);
      if(v-u!=w)s.emplace(u,v),e.emplace_back(u,v,w);
    }
    sort(e.begin(),e.end(),[](tpi x,tpi y){
      return get<2>(x)<get<2>(y);
    });
    dsu d(n);
    for(int i=1;i<n&&c+1<n;i++){
      while(l<e.size()&&get<2>(e[l])<=i&&c+1<n){
        if(!d.same(get<0>(e[l]),get<1>(e[l])))
          d.merge(get<0>(e[l]),get<1>(e[l])),c++,r+=get<2>(e[l]);
        l++;
      }
      for(int j=0;j+i<n&&c+1<n;j++)
        if(s.find(make_pair(j,j+i))==s.end()&&!d.same(j,j+i))
          d.merge(j,j+i),c++,r+=i;
    }
    while(l<e.size()&&c+1<n){
      if(!d.same(get<0>(e[l]),get<1>(e[l])))
        d.merge(get<0>(e[l]),get<1>(e[l])),c++,r+=get<2>(e[l]);
      l++;
    }
    cout<<r<<'\n';
  }
  return 0;
}